10.48 Suppose that the edges in an undirected graph G satisfy the triangle inequality: cu,v + cv,w ≥ cu,w. Show how to compute a traveling salesman tour of cost at most twice optimal. (Hint: Construct a minimum spanning tree.). - | |
| View Solution | |
| << Back | Next >> |